package cn.walls1717.dataStructure.sort;

import cn.walls1717.leetcode.util.AlgorithmUtil;

import java.util.Arrays;

/**
 * 冒泡排序
 *
 * @author walls1717
 * @since 2022-04-28
 **/
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3, 1, 5, 2, 4};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void bubbleSort(int[] arr) {
        // 判断数组比较到哪里结束（已经比较过，排好序的就不再重复比较）
        int n = arr.length - 1;
        // 临时存储最后一次交换的i的位置
        int last;
        do {
            last = 0;
            for (int i = 0; i < n; ++i) {
                if (arr[i] > arr[i + 1]) {
                    AlgorithmUtil.swap(arr, i, i + 1);
                    last = i;
                }
            }
            n = last;
        // 当n为0的时候证明排序完毕，结束循环
        } while (n != 0);
    }
}
